1. Field of the Invention
This invention relates to a method and apparatus for matching positions of images. This invention particularly relates to an improvement in position matching of two images of a single same object.
2. Description of the Related Art
Techniques for comparing at least two images of a single same object, finding a difference between the images, and making an examination of the object, or the like, in accordance with the difference between the images have heretofore been conducted in various fields.
For example, in the fields of production of industrial products, there have heretofore been conducted techniques for comparing an image of a certain product, which image has been recorded when the product is in a state of a new article, and an image of the product, which image has been recorded after a durability test has been made on the product, paying attention to part of the product, at which the difference between the images is large, and determining part of the product, at which the durability is to be enhanced. Also, in the medical fields, there have heretofore been conducted techniques for comparing a plurality of radiation images of a certain diseased part of a patient, which radiation images have been recorded in a time series mode, with one another, finding the condition of advance of the disease or the condition of cure of the disease, and determining a plan for treatment of the disease.
As described above, the techniques for comparing at least two images are conducted ordinarily in various fields. For making the comparison of the at least two images, the at least two images are often displayed on an image display device, and the like. Specifically, the images having been recorded are transformed into image density signals or luminance signals, and visible images are reproduced from the image density signals or luminance signals and displayed on the image display device, and the like. Alternatively, visible images are reproduced on a medium, such as film, by the utilization of a printer.
In cases where at least two images, which are to be compared with each other, are outputted, the images are ordinarily outputted so as to stand side by side with each other. In cases where the comparison is made, a matter of primary concern for the person, who sees the outputted images, is the difference between the images. However, it is not easy to find the difference between the images, which are merely located so as to stand side by side with each other. Particularly when the difference is small, it is difficult to find the difference in the manner described above. Therefore, there is a strong demand for enhancement of performance of the comparison.
Accordingly, ordinarily, techniques for performing inter-image operation processing, such as a subtraction process, on corresponding pixels in the at least two images to be compared with each other, and thereby extracting and enhancing the difference between the images are conducted. In cases where only the difference between the images is thus extracted and enhanced, the difference between the images is capable of being reliably perceived by the person, who sees the outputted image. As a result, the diseased part, which is advancing or curing, is capable of being found reliably.
In cases where the inter-image operation processing is to be performed, it is necessary that positions of the two images, which are to be subjected to the comparison, i.e. the inter-image operation processing, be accurately matched with each other. If the positions of the two images are not accurately matched with each other, an artifact of structures embedded in the images will occur from the inter-image operation processing, which is performed on the corresponding pixels in the images.
Besides the images having been recorded successively in the time series mode, two images, which have been acquired at two different points of time apart from each other, are often subjected to the comparison. In such cases, particularly, a shift often occurs between the two acquired images due to a deviation in orientation of the object during the image recording operation, error, and the like. Therefore, before the inter-image operation processing is performed, it is necessary for the shift to be compensated for.
Accordingly, techniques for matching positions of images have been proposed in, for example, Japanese Unexamined Patent Publication Nos. 7(1995)-37074 and 8(1996)-335721. The proposed techniques for matching positions of images comprise the steps of:
setting a plurality of template regions, which are small regions, in one of the two images of a single same object, which images are to be compared with each other,
setting a plurality of search regions, each of which corresponds to one of the template regions having been set in the one image and is larger than each of the template regions, in the other image,
determining a subregion in each of the search regions, in which subregion an image pattern approximately coincides with the image pattern within the corresponding template region, the determination being performed with respect to each of sets of the template regions and the corresponding search regions, and
performing nonlinear strain transform processing (i.e., warping, e.g., nonlinear strain transform processing utilizing curve fitting with two-dimensional polynomials) on either one of the two images and in accordance with corresponding position relationships between the template regions in the one image and the subregions in the other image, such that the two regions approximately coincide with each other.
In the proposed techniques for matching positions of images, before the position matching processing described above (local position matching processing) is performed, a linear transform, such as an affine transform, comprising rotating processing and/or parallel translation, may be performed, and position matching may thereby be performed to a certain extent.
However, for example, in cases where image patterns of similar textures are embedded in adjacent local area limited regions as in the cases of rib image patterns in chest radiation images, even after the position matching processing described above has been performed, a shift often remains between certain local area limited regions.
Also, in cases where corresponding positions between the local area limited regions are to be determined, the accuracy of the position matching between the local area limited regions is capable of being enhanced by setting the size of each template region to be small. Therefore, the size of each template region should preferably be set to be as small as possible. However, if the small region is merely utilized for determining the subregion in a good position matching state (i.e., the optimum corresponding position), problems will often occur in that the highest degree of coincidence is obtained accidentally with respect to a subregion, which is not the correct optimum corresponding position, within the search region. In such cases, there is the risk that the image pattern within the local area limited region will distort unnaturally.
The primary object of the present invention is to provide a method of matching positions of images, wherein a shift between two images is capable of being suppressed more reliably than with conventional image position matching techniques and is capable of being eliminated accurately, such that an image obtained from position matching is prevented from becoming distorted unnaturally.
Another object of the present invention is to provide an apparatus for carrying out the method of matching positions of images.
A method and apparatus for matching positions of images in accordance with the present invention are characterized by successively reducing a size of a template region and/or a size of a corresponding search region in two images, successively calculating corresponding position relationships such that a degree of image pattern coincidence becomes high, calculating an ultimate corresponding position relationship in accordance with the respective corresponding position relationships, and position matching is performed in accordance with the ultimate corresponding position relationship, such that a shift between the two images is suppressed more reliably than with conventional image position matching techniques and is eliminated accurately, and such that an image obtained from the position matching is prevented from becoming distorted unnaturally.
Specifically, the present invention provides a method of matching positions of images, in which positions of two images of a single same object are matched with each other, the method comprising the steps of:
i) setting a plurality of template regions in one of the two images,
ii) setting a plurality of search regions in the other image, each of which search regions corresponds to one of the template regions,
iii) determining a subregion within each of the search regions, in which subregion a degree of image pattern coincidence with the corresponding template region is high,
iv) calculating a corresponding position relationship between each of the template regions and the corresponding subregion,
v) iterating operations, in which at least either one of a size of the search region and a size of a search range is reduced in stages, the template region and the search region are set in accordance with the corresponding position relationship having been calculated, and a corresponding position relationship between the template region and the corresponding subregion is calculated successively, an ultimate corresponding position relationship being thereby calculated, and
vi) performing transform processing (e.g., nonlinear strain transform processing utilizing, for example, curve fitting with two-dimensional polynomials performed on an entire image area, or transform processing with linear interpolating operations with respect to each of local area limited regions) on at least either one of the two images and in accordance with the thus calculated ultimate corresponding position relationship, the positions of the two images being thereby matched with each other.
The term xe2x80x9csearch rangexe2x80x9d as used herein means the range, over which the template region is capable of moving within the search region. Specifically, for example, in cases where the template region and the search region have rectangular shapes, the size of the template region is represented by (Wt, Wt), and the size of the search region is represented by (Ws, Ws), the size of the search range may be represented by (Ws-Wt, Ws-Wt), where Wsxe2x89xa7Wt. More specifically, the term xe2x80x9creducing a size of a search rangexe2x80x9d as used herein means, for example, the cases where the size of the search region is kept unchanged and the size of the template region is set to be large, and the cases where the size of the template region is kept unchanged and the size of the template region is set to be small.
In the method of matching positions of images in accordance with the present invention, in cases where at least either one of the size of the search region and the size of the search range is reduced in stages, and the template region and the search region are set in accordance with the corresponding position relationship having been calculated, the size of the template region may also be reduced in stages. Specifically, the term xe2x80x9creducing at least either one of a size of a search region and a size of a search range in stagesxe2x80x9d as used herein means that, on the premise that at least either one of the size of the search region and the size of the search range is reduced in stages, the size of the template region may also be reduced in cases where at least either one of the size of the search region and the size of the search range is reduced in stages. The term does not contain the cases where the size of the template region alone is reduced.
Also, in the method of matching positions of images in accordance with the present invention, the object may be one of various objects, such as human bodies, animals, plants, industrial products, geographical features, celestial structures, and scenes. The two images, which are to be subjected to the position matching processing, object should preferably be the images subjected to inter-image operation processing, in which the position matching should be performed at a high accuracy. The inter-image operation processing should preferably be a subtraction process performed on corresponding pixels in the two images. In such cases, the subtraction process may be a simple subtraction or a weighted subtraction. An inter-image operation processed image, which has been obtained from the subtraction process, is ordinarily referred to as the subtraction image. By way of example, the subtraction image maybe an energy subtraction image obtained with the simple subtraction or the weighted subtraction performed on two original images, which have been formed with radiation having different energy distributions and approximately simultaneously in a time series mode (one of which is a high energy image having been formed with radiation having a high energy level, i.e. an ordinary radiation image, and the other of which is a low energy image having been formed with radiation having a low energy level, i.e. a high energy suppressed image). Alternatively, the subtraction image may be a temporal (time difference) subtraction image obtained from two original images, which have been recorded at two different points of time apart from each other in the time series mode. As another alternative, the subtraction image may be a digital subtraction angiography image obtained from two original images of blood vessels, which images have been recorded before injection of contrast media and after injection of the contrast media.
As described above, the two images of the single same object may be, for example, the two radiation images of an identical site of the single same object, which images have been recorded at two different points of time apart from each other in the time series mode. However, the two images of the single same object are not limited to the two radiation images described above, and the like. For example, the two images of the single same object may be two image areas, which are embedded in a single image and which represent sites having approximately identical shapes (e.g., the right and left lungs, or the right and left mammae). Specifically, the two images are not limited to two different images and may be two different image areas embedded in a single same image.
The two images described above should preferably be the medical radiation images.
The setting of the template regions and the corresponding search regions for the position matching processing may be performed over the entire areas of the two images to be subjected to the position matching processing. Alternatively, the setting of the template regions and the corresponding search regions for the position matching processing may be performed with respect to only the local area limited regions, between which there is a shift (a degree of shift is high).
In cases where the template regions and the corresponding search regions for the position matching processing are to be set with respect to only certain local area limited regions, the method of matching positions of images in accordance with the present invention may be modified such that local area limited regions, between which a degree of shift is high, in the two images are set (manually and arbitrarily) prior to the setting of the template regions and the corresponding search regions, and
the template regions and the corresponding search regions are set with respect to only the local area limited regions, which have thus been set.
Alternatively, in cases where the template regions and the corresponding search regions for the position matching processing are to be set with respect to only certain local area limited regions, the method of matching positions of images in accordance with the present invention may be modified such that local area limited regions, between which a degree of shift is high, are selected (automatically) prior to the setting of the template regions and the corresponding search regions by (automatically) setting a plurality of local area limited regions in one of the two images (regardless of the degree of shift), setting a plurality of local area limited regions, each of which corresponds to one of the local area limited regions in the one image, in the other image (regardless of the degree of shift), calculating the degree of shift between corresponding local area limited regions in the two images and with respect to each of sets of the corresponding local area limited regions in the two images, and (automatically) selecting the local area limited regions, between which the degree of shift is high, in the two images in accordance with the thus calculated degrees of shift, and
the template regions and the corresponding search regions are set with respect to only the local area limited regions, which have thus been selected.
The term xe2x80x9cprior to setting of template regions and corresponding search regionsxe2x80x9d as used herein means every point of time, at which the template regions and the corresponding search regions are set in the two images. The term means the point of time, at which the template regions and the corresponding search regions are set originally, and each of the points of time, at which at least either one of the size of the search region and the size of the search range is reduced in stages, and the template region and the search region are set in accordance with the corresponding position relationship having been calculated. Specifically, the term xe2x80x9csetting template regions and corresponding search regions with respect to only local area limited regions having been set (or selected)xe2x80x9d as used herein means that the template regions and the corresponding search regions in accordance with the point of time, at which the setting of the local area limited regions has been performed, are set, and the operations are iterated, in which at least either one of the size of the search region and the size of the search range is reduced in stages in the local area limited regions, the template region and the search region are set in the local area limited regions and in accordance with the corresponding position relationship having been calculated, and a corresponding position relationship between the template region and the corresponding subregion is calculated successively. More specifically, for example, in cases where the local area limited regions have been set (or selected) prior to the setting of the template regions and the corresponding search regions in a second stage, the template regions and the corresponding search regions in the second stage are set with respect to only the local area limited regions having thus been set (or selected), and a corresponding position relationship between the template region and the corresponding subregion is calculated successively. In such cases, thereafter, the ultimate corresponding position relationship may be calculated with respect to only the local area limited regions having thus been set (or selected).
As a technique for automatically setting the local area limited regions over the entire areas of the two images and automatically selecting the local area limited regions, in which the template region and the corresponding search region are to be set, a technique may be employed, wherein the degree of shift between the corresponding local area limited regions is calculated as a total sum value of absolute values of pixel value differences between corresponding pixels in the corresponding local area limited regions in the two images, and the selection of the local area limited regions, between which the degree of shift is high, is made by performing threshold value processing on the total sum value of the absolute values of the pixel value differences between the corresponding pixels in the corresponding local area limited regions.
As the corresponding local area limited regions in the two images, regions having their centerpoints at identical spatial coordinates and having an identical shape (e.g., rectangular regions) in the two images may be employed.
In cases where the template regions and the corresponding search regions are capable of being set with respect to only the certain local area limited regions in the images in the manner described above, before the position matching processing with the method of matching positions of images in accordance with the present invention is performed, the technique for matching positions of images proposed in, for example, Japanese Unexamined Patent Publication No. 7(1995)-37074 or 8(1996)-335721, a linear transform, such as an affine transform, or the like, is capable of being performed as approximate position matching processing. Thereafter, the position matching processing with the method of matching positions of images in accordance with the present invention is capable of being performed as position re-matching processing in accordance with a shift between local area limited regions, for which the position matching could not be achieved appropriately with the approximate position matching processing.
Further, the method of matching positions of images in accordance with the present invention may be modified such that a first corresponding position relationship is calculated by:
setting a first template region in a local area limited region in one of the two images, the setting of the first template region being performed with respect to each of sets of corresponding local area limited regions in the two images, for which local area limited regions the determination of the subregion is to be performed,
setting a first search region, which has a size larger than the size of the first template region, in the local area limited region in the other image, the setting of the first search region being performed with respect to each of the sets of the corresponding local area limited regions in the two images, for which local area limited regions the determination of the subregion is to be performed,
determining a first subregion within the first search region, in which subregion the degree of image pattern coincidence with the first template region is high, the determination of the first subregion being performed with respect to each of sets of the first template regions and the corresponding first search regions within the corresponding local area limited regions in the two images, and
calculating a corresponding position relationship between each of the first template regions and the corresponding first subregion as the first corresponding position relationship,
a second corresponding position relationship is calculated by:
setting a second template region, which has a size smaller than the size of the first template region, in the local area limited region in the one image, the setting of the second template region being performed in accordance with the first corresponding position relationship and with respect to each of the sets of the corresponding local area limited regions in the two images, for which local area limited regions the determination of the subregion is to be performed,
setting a second search region, which has a size larger than the size of the second template region and smaller than the size of the first search region, in the local area limited region in the other image, the setting of the second search region being performed with respect to each of the sets of the corresponding local area limited regions in the two images, for which local area limited regions the determination of the subregion is to be performed,
determining a second subregion within the second search region, in which subregion the degree of image pattern coincidence with the second template region is high, the determination of the second subregion being performed with respect to each of sets of the second template regions and the corresponding second search regions within the corresponding local area limited regions in the two images, and
calculating a corresponding position relationship between each of the second template regions and the corresponding second subregion as the second corresponding position relationship,
an n-th corresponding position relationship (nxe2x89xa73) is calculated by iterating the setting of template regions and search regions, the determination of subregions, and the calculation of corresponding position relationships, when necessary, the ultimate corresponding position relationship between each of the template regions and the corresponding subregion being thereby calculated, and
the positions of the two images are matched with each other in accordance with the ultimate corresponding position relationship.
In such cases, at the stage, at which the second corresponding position relationship has been calculated, the ultimate corresponding position relationship between each of the template regions and the corresponding subregion may be calculated.
Also, in such cases, the degree of image pattern coincidence between the first template region and the first subregion should preferably be calculated in accordance with a normalized cross correlation value, and
the degree of image pattern coincidence between the second template region and the second subregion, and the degree of image pattern coincidence between each of the template regions that follow and each of the corresponding subregions that follow should preferably be calculated in accordance with a total sum value of absolute values of pixel value differences between corresponding pixels in the template region and the corresponding subregion in the two images.
Alternatively, the degree of image pattern coincidence in every stage may be calculated in accordance with the normalized cross correlation value. As another alternative, the degree of image pattern coincidence in every stage may be calculated in accordance with the total sum value of the absolute values of the pixel value differences between the corresponding pixels in the template region and the corresponding subregion in the two images.
In the method of matching positions of images in accordance with the present invention and in an apparatus for matching positions of images in accordance with the present invention, which will be described later, a processing for matching the position of one of the two images with the position of the other image may be performed in accordance with the corresponding position relationship, which has been calculated, between adjacent stages associated with the operations, in which at least either one of the size of the search region and the size of the search range is reduced in stages, the template region and the search region are set in accordance with the corresponding position relationship having been calculated, and a corresponding position relationship between the template region and the corresponding subregion is calculated successively. Specifically, for example, in a stage between when the first corresponding position relationship has been calculated and when the second template region and the second search region are set, the processing for matching the position of one of the two images with the position of the other image may be performed in accordance with the first corresponding position relationship. (Also, in the same manner, in a stage between when the second corresponding position relationship has been calculated and when the third template region and the third search region are set, position matching may be performed on the two images, whose positions have been matched with each other in accordance with the first corresponding position relationship, and in accordance with the second corresponding position relationship. In this manner, before the template region and the search region are set in each stage, position matching may be performed in accordance with the corresponding position relationship, which has been calculated in the preceding stage.) In such cases, the ultimate corresponding position relationship is not an accumulated corresponding position relationship, which is obtained by accumulating the corresponding position relationships calculated in the respective stages. The n-th corresponding position relationship between the n-th subregion, which is determined in accordance with the n-th template region and the n-th search region having been set ultimately, and the n-th template region acts as the ultimate corresponding position relationship.
The present invention also provides a first apparatus for carrying out the method of matching positions of images in accordance with the present invention. Specifically, the present invention also provides an apparatus for matching positions of images, in which positions of two images of a single same object are matched with each other, the apparatus comprising:
position matching processing means for:
setting a plurality of template regions in one of the two images,
setting a plurality of search regions in the other image, each of which search regions corresponds to one of the template regions,
determining a subregion within each of the search regions, in which subregion a degree of image pattern coincidence with the corresponding template region is high,
calculating a corresponding position relationship between each of the template regions and the corresponding subregion,
iterating operations, in which at least either one of a size of the search region and a size of a search range is reduced in stages, the template region and the search region are set in accordance with the corresponding position relationship having been calculated, and a corresponding position relationship between the template region and the corresponding subregion is calculated successively, in order to calculate an ultimate corresponding position relationship, and
performing transform processing on at least either one of the two images and in accordance with the thus calculated ultimate corresponding position relationship in order to match the positions of the two images with each other.
As described above, the term xe2x80x9csearch rangexe2x80x9d as used herein means the range, over which the template region is capable of moving within the search region.
The present invention further provides a second apparatus for matching positions of images, in which positions of two images of a single same object are matched with each other, the apparatus comprising:
i) approximate position matching processing means for performing approximate position matching processing with respect to entire areas of the two images by performing transform processing comprising at least one kind of processing, which is among rotating processing, parallel translation, and image size enlargement or reduction processing, on the entire area of at least either one of the two images, and
ii) position matching processing means for:
setting a plurality of template regions in one of the two images, whose positions have been approximately matched with each other by the approximate position matching processing means,
setting a plurality of search regions in the other image, each of which search regions corresponds to one of the template regions,
determining a subregion within each of the search regions, in which subregion a degree of image pattern coincidence with the corresponding template region is high,
calculating a corresponding position relationship between each of the template regions and the corresponding subregion,
iterating operations, in which at least either one of a size of the search region and a size of a search range is reduced in stages, the template region and the search region are set in accordance with the corresponding position relationship having been calculated, and a corresponding position relationship between the template region and the corresponding subregion is calculated successively, in order to calculate an ultimate corresponding position relationship, and
performing transform processing on at least either one of the two images and in accordance with the thus calculated ultimate corresponding position relationship in order to match the positions of the two images with each other.
The first and second apparatuses for matching positions of images in accordance with the present invention may be modified such that, in cases where the position matching processing means reduces at least either one of the size of the search region and the size of the search range in stages and sets the template region and the search region in accordance with the corresponding position relationship having been calculated, the position matching processing means also reduces the size of the template region in stages.
The setting of the template regions and the corresponding search regions by the position matching processing means may be performed over the entire areas of the two images to be subjected to the position matching processing. Alternatively, the setting of the template regions and the corresponding search regions by the position matching processing means may be performed with respect to only the local area limited regions, between which there is a shift (the degree of shift is high). Specifically, in cases where the setting of the template regions and the corresponding search regions by the position matching processing means is to be performed with respect to only certain local area limited regions, each of the first and second apparatuses for matching positions of images in accordance with the present invention may be modified such that the apparatus further comprises position matching region setting means for (manually and arbitrarily) setting local area limited regions, between which a degree of shift is high, in the two images prior to the setting of the template regions and the corresponding search regions, and
the position matching processing means sets the template regions and the corresponding search regions with respect to only the local area limited regions, which have been set by the position matching region setting means, and calculates the ultimate corresponding position relationship.
Alternatively, in cases where the setting of the template regions and the corresponding search regions by the position matching processing means is to be performed with respect to only certain local area limited regions, each of the first and second apparatuses for matching positions of images in accordance with the present invention may be modified such that the apparatus further comprises position matching region selecting means for (automatically) selecting local area limited regions, between which a degree of shift is high, prior to the setting of the template regions and the corresponding search regions by (automatically) setting a plurality of local area limited regions in one of the two images (regardless of the degree of shift), setting a plurality of local area limited regions, each of which corresponds to one of the local area limited regions in the one image, in the other image (regardless of the degree of shift), calculating the degree of shift between corresponding local area limited regions in the two images and with respect to each of sets of the corresponding local area limited regions in the two images, and (automatically) selecting the local area limited regions, between which the degree of shift is high, in the two images in accordance with the thus calculated degrees of shift, and
the position matching processing means sets the template regions and the corresponding search regions with respect to only the local area limited regions, which have been selected by the position matching region selecting means, and calculates the ultimate corresponding position relationship.
As described above, the term xe2x80x9cprior to setting of template regions and corresponding search regionsxe2x80x9d as used herein means every point of time, at which the template regions and the corresponding search regions are set in the two images The term xe2x80x9csetting template regions and corresponding search regions with respect to only local area limited regions having been set (or selected)xe2x80x9d as used herein means that the template regions and the corresponding search regions in accordance with the point of time, at which the setting of the local area limited regions has been performed, are set, and the operations are iterated, in which at least either one of the size of the search region and the size of the search range is reduced in stages in the local area limited regions, the template region and the search region are set in the local area limited regions and in accordance with the corresponding position relationship having been calculated, and a corresponding position relationship between the template region and the corresponding subregion is calculated successively.
In the position matching region selecting means, as a technique for automatically setting the local area limited regions over the entire areas of the two images and automatically selecting the local area limited regions, in which the template region and the corresponding search region are to be set, a technique may be employed, wherein the degree of shift between the corresponding local area limited regions is calculated as a total sum value of absolute values of pixel value differences between corresponding pixels in the corresponding local area limited regions in the two images, and the selection of the local area limited regions, between which the degree of shift is high, is made by performing threshold value processing on the total sum value of the absolute values of the pixel value differences between the corresponding pixels in the corresponding local area limited regions.
In cases where the template regions and the corresponding search regions are capable of being set with respect to only the certain local area limited regions in the images in the manner described above, each of the first and second apparatuses for matching positions of images in accordance with the present invention may further comprise pre-processing means for performing the technique for matching positions of images proposed in, for example, Japanese Unexamined Patent Publication No. 7(1995)-37074 or 8(1996)-335721, a linear transform, such as an affine transform, or the like, as approximate position matching processing, or the like, before the position matching processing with the position matching processing means of the apparatus for matching positions of images in accordance with the present invention is performed. Thereafter, the position matching processing with the position matching processing means of the apparatus for matching positions of images in accordance with the present invention is capable of being performed as position re-matching processing in accordance with a shift between local area limited regions, for which the position matching could not be achieved appropriately with the approximate position matching processing performed by the pre-processing means. In this manner, the position matching is capable of being performed more accurately.
Further, each of the first and second apparatuses for matching positions of images in accordance with the present invention may be modified such that the position matching processing means comprises spring constraint processing means for performing spring constraint processing in at least one stage among the stages of setting the template region and the search region, the spring constraint processing comprising:
taking every template region in one of the two images and the corresponding subregion in the other image as center regions,
taking a plurality of template regions, which surround the center region in the one image, and a plurality of the subregions, which surround the center region in the other image and correspond to the plurality of the template regions, as surrounding regions,
constraining the corresponding position relationship, which has been calculated with respect to the corresponding center regions in the two images, and each of the corresponding position relationships, which have been calculated with respect to sets of corresponding surrounding regions in the two images, with each other, the constraint being performed with constraining forces in accordance with the corresponding position relationship, which has been calculated with respect to the corresponding center regions in the two images, and the corresponding position relationships, which have been calculated with respect to the sets of the corresponding surrounding regions in the two images, and
calculating a new relative corresponding position relationship with respect to the center regions in accordance with the constraining forces, and
the position matching processing means utilizes the new relative corresponding position relationship, which has been calculated by the spring constraint processing means and with respect to each of sets of the center regions in the two images, as the corresponding position relationship between the template region and the corresponding subregion in the at least one stage.
The term xe2x80x9cstages of setting a template region and a search regionxe2x80x9d as used herein means the stages of reducing at least either one of the size of the search region and the size of the search range in stages and setting the template region and the search region, and the original stage of setting the template region and the search region.
Furthermore, each of the first and second apparatuses for matching positions of images in accordance with the present invention may be modified such that the position matching processing means is means for:
calculating a first corresponding position relationship by:
setting a first template region in a local area limited region in one of the two images, the setting of the first template region being performed with respect to each of sets of corresponding local area limited regions in the two images, for which local area limited regions the determination of the subregion is to be performed,
setting a first search region, which has a size larger than the size of the first template region, in the local area limited region in the other image, the setting of the first search region being performed with respect to each of the sets of the corresponding local area limited regions in the two images, for which local area limited regions the determination of the subregion is to be performed,
determining a first subregion within the first search region, in which subregion the degree of image pattern coincidence with the first template region is high, the determination of the first subregion being performed with respect to each of sets of the first template regions and the corresponding first search regions within the corresponding local area limited regions in the two images, and
calculating a corresponding position relationship between each of the first template regions and the corresponding first subregion as the first corresponding position relationship,
calculating a second corresponding position relationship by:
setting a second template region, which has a size smaller than the size of the first template region, in the local area limited region in the one image, the setting of the second template region being performed in accordance with the first corresponding position relationship and with respect to each of the sets of the corresponding local area limited regions in the two images, for which local area limited regions the determination of the subregion is to be performed,
setting a second search region, which has a size larger than the size of the second template region and smaller than the size of the first search region, in the local area limited region in the other image, the setting of the second search region being performed with respect to each of the sets of the corresponding local area limited regions in the two images, for which local area limited regions the determination of the subregion is to be performed,
determining a second subregion within the second search region, in which subregion the degree of image pattern coincidence with the second template region is high, the determination of the second subregion being performed with respect to each of sets of the second template regions and the corresponding second search regions within the corresponding local area limited regions in the two images, and
calculating a corresponding position relationship between each of the second template regions and the corresponding second subregion as the second corresponding position relationship,
calculating an n-th corresponding position relationship by iterating the setting of template regions and search regions, the determination of subregions, and the calculation of corresponding position relationships, when necessary, in order to calculate the ultimate corresponding position relationship between each of the template regions and the corresponding subregion, and
matching the positions of the two images with each other in accordance with the ultimate corresponding position relationship.
In such cases, the position matching processing means should preferably operate such that the degree of image pattern coincidence between the first template region and the first subregion is calculated in accordance with a normalized cross correlation value, and
the degree of image pattern coincidence between the second template region and the second subregion, and the degree of image pattern coincidence between each of the template regions that follow and each of the corresponding subregions that follow are calculated in accordance with a total sum value of absolute values of pixel value differences between corresponding pixels in the template region and the corresponding subregion in the two images.
Alternatively, the degree of image pattern coincidence in every stage may be calculated in accordance with the normalized cross correlation value. As another alternative, the degree of image pattern coincidence in every stage may be calculated in accordance with the total sum value of the absolute values of the pixel value differences between the corresponding pixels in the template region and the corresponding subregion in the two images.
In the aforesaid processing for reducing at least either one of the size of the search region and the size of the search range in stages and calculating the ultimate corresponding position relationship, in cases where an (n+1)-th template region and an (n+1)-th search region are to be set in accordance with the n-th corresponding position relationship, the same number of the (n+1)-th template regions as the number of the n-th template regions, which have already been set, may be set at the positions approximately identical with the positions of the n-th template regions, and the same number of the (n+1)-th search regions as the number of the n-th search regions, which have already been set, may be set at the positions approximately identical with the positions of the n-th search regions. Alternatively, a number of the (n+1)-th template regions larger than the number of the n-th template regions, which have already been set, and a number of the (n+1)-th search regions larger than the number of the n-th search regions, which have already been set, may be set.
With the method and apparatuses for matching positions of images in accordance with the present invention, with respect to the two images to be subjected to the position matching processing, at least either one of the size of the template region and the size of the corresponding search region in the two images is reduced successively, and the template region and the corresponding search region are set successively in accordance with the corresponding position relationship, which has been calculated. Also, the corresponding position relationships are calculated successively such that the degree of image pattern coincidence becomes high, and the position matching is performed in accordance with the ultimate corresponding position relationship, which is calculated ultimately. Therefore, the shift between the two images is capable of being suppressed more reliably than with the conventional image position matching techniques and is capable of being eliminated accurately. Also, the image obtained from the position matching is capable of being prevented from becoming distorted unnaturally.
Specifically, with the method and apparatuses for matching positions of images in accordance with the present invention, at least either one of the size of the template region and the size of the corresponding search region in the two images is reduced successively, and the template region and the corresponding search region are set successively in accordance with the corresponding position relationship, which has been calculated. Therefore, the ranges of the regions, whose positions are to be matched with each other, become small in stages. As a result, the accuracy, with which the positions of the corresponding local area limited regions in the two images are matched with each other, is capable of being enhanced.
In such cases, in order for the position matching accuracy to be enhanced, the sizes of the regions (i.e., the template region and the search region) utilized for calculating the corresponding positions should preferably be as small as possible. However, if the small regions are merely utilized for calculating the corresponding positions in a good position matching state (i.e., the optimum corresponding positions), a local minimum phenomenon, wherein the highest degree of coincidence is obtained with respect to a subregion, which is not the correct optimum corresponding position, within the search region, will often occur. In such cases, the problems will occur in that the optimum corresponding position, which is calculated for each of the local area limited regions, becomes a position which is capable of being obtained only when the local area limited region is translated in a direction markedly different from the direction of translation of an adjacent local area limited region. As a result, the image pattern within the local area limited region will distort unnaturally.
Therefore, with the method and apparatuses for matching positions of images in accordance with the present invention, as described above, in order for the optimum corresponding positions to be calculated, the corresponding position relationships are calculated in stages by reducing the sizes of the regions in stages. Accordingly, the local minimum phenomenon is capable of being prevented from occurring, and the image pattern within the local area limited region is capable of being prevented from distorting unnaturally.
With the apparatuses for matching positions of images in accordance with the present invention, wherein the position matching processing means comprises the spring constraint processing means, the corresponding position relationship between the corresponding regions in the two images is smoothed in accordance with the corresponding position relationships, which have been calculated with respect to the sets of the surrounding regions. Therefore, the position matching accuracy is capable of being enhanced even further.